package 算法基础模板.chapter_04;

/**
 * 快速幂
 * <p>
 * int qmi(int m, int k, int p)
 * {
 * int res = 1 % p, t = m;
 * while (k)
 * {
 * if (k&1) res = res * t % p;
 * t = t * t % p;
 * k >>= 1;
 * }
 * return res;
 * }
 *
 *
 *  3 ^ 1000000
 *  <p>
 *  3 ^ 1 = 3
 *  3 ^ 2 = 9
 *  3 ^ 4 = 81
 *  3 ^ 8 =
 *  <p>
 *  3 ^ (2 ^ 19)
 * @author Summerday
 */
public class Qmi {

    // 求 m^k mod p，时间复杂度 O(logk)。
    int qmi (int m, int k, int p) {
        int res = 1 % p, t = m;
        while (k > 0) {
            if ((k & 1) == 1) res = res * t % p;
            t = t * t % p;
            k >>= 1;
        }
        return res;
    }


}
